`
https://leetcode.cn/problems/freedom-trail/
`

/**
 * @param {string} ring
 * @param {string} key
 * @return {number}
 */
var findRotateSteps = function (ring, key) {
  const memo = new Array(ring.length).fill().map(() => new Array(key.length).fill(0))
  const charToIdx = new Map()
  // 记录圆环上字符到索引的映射
  for (let i = 0; i < ring.length; i++) {
    const c = ring[i];
    if (!charToIdx.has(c)) {
      charToIdx.set(c, [])
    }
    charToIdx.get(c).push(i);
  }

  // 计算圆盘指针在 ring[i]，输入 key[j..] 的最少操作数
  function dp(i, j) {
    // 完成输入
    if (j === key.length) {
      return 0
    }

    // 已经计算过
    if (memo[i][j] !== 0) {
      return memo[i][j]
    }

    let res = Infinity
    // ring 里可能有多个 key[j]
    for (const k of charToIdx.get(key[j])) {
      // 转盘波动次数
      let delta = Math.abs(k - i)
      // 顺时针还是逆时针
      delta = Math.min(delta, ring.length - delta)
      // 将指针拨到 ring[k]，继续输入 key[j+1..]
      const subProblem = dp(k, j + 1)
      // 选择「整体」操作次数最少的
      // 加一是因为按动按钮也是一次操作
      res = Math.min(res, 1 + delta + subProblem)
    }

    memo[i][j] = res
    return res
  }

  return dp(0, 0)
};